package github._3y.datastructure.tree;

/**
 * @Auther DRevelation
 * @Date 2020-06-05 上午 11:17
 * @Desc
 */
public class TreeTest {
    public static void main(String[] args) {

        int[] arr = {3, 2, 7, 4, 5};

        TreeRoot root = new TreeRoot();
        for (int i = 0; i < arr.length; i++) {
            createTree(root, arr[i]);
        }
        System.out.println("======先序遍历======");
        preTraverse(root.getRoot());
        System.out.println("======中序遍历=====");
        inTraverse(root.getRoot());

        System.out.println("树的深度是：" + getHeight(root.getRoot()));
        System.out.println("树的最大值是：" + getMax(root.getRoot()));
    }

    private static void createTree(TreeRoot root, int value) {
        if (root.getRoot() == null) {
            TreeNode node = new TreeNode(value);
            root.setRoot(node);
        } else {
            TreeNode tempRoot = root.getRoot();
            while (tempRoot != null) {
                if (value > tempRoot.getValue()) {
                    if (tempRoot.getRightTreeNode() == null) {
                        tempRoot.setRightTreeNode(new TreeNode(value));
                        return;
                    } else {
                        tempRoot = tempRoot.getRightTreeNode();
                    }
                } else {
                    if (tempRoot.getLeftTreeNode() == null) {
                        tempRoot.setLeftTreeNode(new TreeNode(value));
                        return;
                    } else {
                        tempRoot = tempRoot.getLeftTreeNode();
                    }
                }
            }
        }
    }

    private static void preTraverse(TreeNode rootTreeNode) {
        if (rootTreeNode != null) {
            preTraverse(rootTreeNode.getLeftTreeNode());
            System.out.println(rootTreeNode.getValue());
            preTraverse(rootTreeNode.getRightTreeNode());
        }
    }

    private static void inTraverse(TreeNode rootTreeNode) {
        if (rootTreeNode != null) {
            System.out.println(rootTreeNode.getValue());
            inTraverse(rootTreeNode.getLeftTreeNode());
            inTraverse(rootTreeNode.getRightTreeNode());
        }
    }

    private static void afterTraverse(TreeNode rootTreeNode) {
        if (rootTreeNode != null) {
            afterTraverse(rootTreeNode.getLeftTreeNode());
            afterTraverse(rootTreeNode.getRightTreeNode());
            System.out.println(rootTreeNode.getValue());
        }
    }

    private static int getHeight(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        } else {
            int left = getHeight(treeNode.getLeftTreeNode());
            int right = getHeight(treeNode.getRightTreeNode());

            int max = left;
            if (right > max) {
                max = right;
            }
            return max + 1;
        }
    }

    private static int getMax(TreeNode rootTreeNode) {
        if (rootTreeNode == null) {
            return -1;
        } else {
            int left = getMax(rootTreeNode.getLeftTreeNode());
            int right = getMax(rootTreeNode.getRightTreeNode());

            int currentRootValue = rootTreeNode.getValue();
            int max = left;
            if (right > max) {
                max = right;
            }
            if (currentRootValue > max) {
                max = currentRootValue;
            }
            return max;
        }
    }
}